package jianzhioffer;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/24 9:21
 * 统计一个数字在排序数组中出现的次数。
 */
public class offer_51_1_在排序数组中查找数字1 {

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        System.out.println(search(nums, target));
    }

//    暴力遍历（不推荐）
    public static int search1(int[] nums, int target) {
        int count = 0;
        for (int i=0; i<nums.length; i++){
            if (nums[i] == target) count ++;
        }
        return count;
    }

//    二分法
    public static int search2(int[] nums, int target) {
//        搜索右边界
        int i = 0, j = nums.length - 1;
        while (i <= j){
            int m = (i+j)/2;
            if (nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
//        若数组中无target，提前返回
        if (j >= 0 && nums[j] != target) return 0;
//        搜索左边界
        i = 0; j = nums.length-1;
        while (i <= j){
            int m = (i+j)/2;
            if (nums[m] < target) i = m+1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }

//    只循环一次
    public static int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] < target) {
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                if (nums[low] == nums[high]) {
                    return high - low + 1;
                }
                if (nums[low] < target) {
                    low++;
                }
                if (nums[high] > target) {
                    high--;
                }
            }

        }
        return 0;
    }
}
